Modern parallel/multi-processing systems employ many processor-containing nodes which simultaneously perform multiple tasks that are either related or independent. Each node communicates with all other nodes via a communication network. Each node includes a processor which operates under control of its own operating system and functions as the overseer of all procedures executed within the node. It is often the case that one or more nodes, in the course of performing their respective procedures, will require access to system resources housed on another node or nodes. To prevent contention between nodes for a shared resource, a locking mechanism is provided to guarantee that competing nodes do not simultaneously attempt to use or modify a same shared resource during performance of different procedures. A locking system enables synchronization of the use of shared resources amongst competing nodes and enables organized functioning of the multi-processor system.
As is known, a lock generally constitutes one or more words in a memory which manifest a state indicating whether a resource associated with that lock is busy or free. When a lock request is received and manifests a value that differs from the value of the lock, it is known that the lock is in use and unavailable to the requestor. If, by contrast, a received lock request matches a stored lock value, then it is known that the associated resource is available and steps are taken to (1) grant ownership of the lock to the requesting party and (2) to change the stored lock value so that another requestor will not be able to access the lock.
To enable the described lock protocol, prior art systems have employed a "Compare and Swap" hardware instruction which enables a requestor's lock value to be compared to the stored lock value and, if equality of values is found, to swap in a new value in place of the stored lock word, while simultaneously granting ownership of the lock to the requestor.
The prior art includes various locking schemes which are employed when memory is shared by two or more processors. For instance, in U.S. Pat. No. 4,965,718 to George et al, a memory contains "semaphore" data which indicates the status of a requested resource. A requestor transmits a "directive" which includes an address of a selected memory location, including a semaphore comparison value, and an identification of the requestor. If the semaphore is found to indicate a busy status (a non-comparison), the directive is stored in the selected memory element where the semaphore data is stored and the state of the semaphore data is thereafter monitored until a change occurs. In this manner, controlled access is achieved for the requested resource.
U.S. Pat. No. 5,175,837 to Arnold et al, is a further shared memory system wherein a central memory stores a directory of lock bits. Each lock bit controls a predefined segment of system memory. When the lock bit is set in an unlock state, access to the protected area of memory is allowed. A fairness procedure processes denied lock requests and sequentially positions them in a first come, first served queue.
U.S. Pat. No. 5,115,499 to Stiffler et al, describes a resource control procedure which employs a memory that indicates a current state of the resource and the identity of the processing element currently utilizing the resource. The memory location can be interrogated by any of the processing elements and thereby performs a lock allocation function.
U.S. Pat. No. 5,060,144 to Sipple et al, describes a shared memory system that includes a special lock processor. The lock processor enables requests for objects stored in a shared memory to be properly allocated amongst contending users.
Other prior art systems have employed a "pass the buck" approach to lock management. In such systems, a table containing the state of all locks is passed among nodes comprising the system. The node that has ownership of the lock table has access to the locks listed therein. Substantial processing overhead is required to transfer the lock table between nodes and, in systems where a large number of nodes are present, a substantial latency period may occur between table ownership periods.
As the number of nodes in multi-processing systems have increased (presently being on the order of thousands), it is preferred that any locking mechanism be distributed amongst the nodes, rather than being dependent upon a central controlling processor. Such a distributed feature enables the locking system to be recovered in the event of failure of a node, as contrasted to a possible complete system failure when a central lock processor fails.
As above indicated, a lock processing system is required to enable nodes in a multi-processing system to operate in a synchronous manner. If however, lock processing is software-controlled in a node, substantial amounts of system time need to be allocated to the lock processing function. As a result, overall system performance is degraded when multiple nodes implement simultaneous lock requests during performance of a system-wide procedure.
Accordingly, it is an object of this invention to provide a parallel/multi-processing system with a distributed lock processing procedure.
It is another object of this invention to provide improved lock processing apparatus for a parallel/multi-processing system wherein nodal processor-involvement is minimized.
It is another object of this invention to provide an improved lock processing mechanism which enables plural lock requests from a single requesting node to be handled on an atomic basis.
It is yet another object of this invention to provide an improved locking mechanism for a parallel/multi-processing system which implements lock processing on a real-time hardware basis rather than a software-controlled basis.